#!/usr/env python
#-*-coding: utf-8 -*-

class QuickSort:
    
    def __init__(self):
        """contructor2"""
        pass
    pass
    
    #
    #Algoritmo QuickSort
    #
    def quick_Sort(self, lstA, p_val, r_val):
        """metodo quicksort
        """
        if (p_val < r_val):
            q_val = self.__partition(lstA, p_val, r_val)
            
            self.quick_Sort(lstA, p_val, q_val-1)
            self.quick_Sort(lstA, q_val+1, r_val)
        pass
    pass

    def __partition(self, lstA, p_val, r_val):
        """metodo partition
        """
        x_val = lstA[r_val]
        i_val = p_val - 1
        
        for j in range(p_val, r_val):
            if (lstA[j] <= x_val):                                      #smetimes there is a runtimeErrr here on recursion depth exceeded
                i_val +=1                                               #the explanation I found is that Python recursion depth is 999
                tmp = lstA[i_val]
                lstA[i_val] = lstA[j]
                lstA[j] = tmp
            pass
        pass
        tmp = lstA[i_val +1]
        lstA[i_val +1] = lstA[r_val]
        lstA[r_val] = tmp
        
        return i_val+1
    pass
pass
